package edu.cth.ai23;
public class IDSSolver extends Solver implements IProblemSolver {

    public IDSSolver(IProblem problem) {
        super();
    }
    int oldHeuristic;
    int bestHeuristic;
    int maximumDepth = 20;
    int deepestSearch = 0;
    boolean greed = false; //Variable used for setting the IDS to greedy/non greedy

    public void run() {
        solved = false;        
        final int size = 300;
        Integer[] moves = new Integer[size];
        this.maximumDepth = this.problem.getSearchDepth();
        this.greed = this.problem.getGreed();
        Integer[] newMoves = new Integer[maximumDepth+1];
        boolean solutionFound = true;
        int backTracking = 0;
        int lastMove = -1;
        int minimumDepth = 0;
        int currentHeuristic = this.heuristic();
        
        for (int i = 0; i < size; i++) {
            moves[i] = -1;
        }
        
        long lastTime = System.currentTimeMillis();
        this.timeStarted = lastTime;
        
        while (this.heuristic() != 0 && !this.stop) {
        	int length = searchHandler(newMoves, lastMove, minimumDepth, currentHeuristic);
        	int offset = 0;
        	
        	while(moves[offset]!=-1) {
    			offset++;
    		}	
        	
        	if (length != -1) {
        		minimumDepth = 0;
        		System.out.println("Search successful!");
        		for (int i=0; i<length+1; i++) {
        			moves[offset+i] = newMoves[i];
        			this.problem.move(newMoves[i], this.problem);
        			lastMove = newMoves[i];
        			newMoves[i] = -1;
        			backTracking = 0;
        		}
        		currentHeuristic = this.heuristic();
        		
        	} else if (backTracking < offset) {
        		System.out.println("BackTracking enabled with " + (backTracking+1) + " steps");
        		backTracking++;
        		/*if (backTracking<=maximumDepth) {
        			minimumDepth = backTracking;
        		}*/
        		this.problem.reverseMove(moves[offset-1], this.problem);
        		lastMove = moves[offset-2];
        		moves[offset-1] = -1;
        		
        	} else { 
        		solutionFound = false;
        		break;
        	}
        }
        
        if (solutionFound) {
        	this.report = "solved!\n";
        }
        else {
        	this.report = "not solved!\n";
        }
        
        int solutionSize = 0;
        for (int i = 0; i < size; i++) {
            if (moves[i] != -1) {
            	solutionSize++;
            	this.report = this.report + this.problem.getMoveName(moves[i]) + "\n";
            }
        }
        this.report = this.report + "nr of moves: " + solutionSize + "\n";
        
        synchronized (lock) {
            this.solved = true;
        }
        timeFinished = System.currentTimeMillis();
    }
    
    public int searchHandler(Integer[] newMoves, int lastMove, int startDepth, int heuristic) {
    	oldHeuristic = heuristic;//this.heuristic();
    	bestHeuristic = oldHeuristic;
    	int searchDepth = startDepth;
    	int length = -1;    	    	
    	System.out.println("Starting level " + searchDepth + " search");
    	boolean status = searchIterating(searchDepth, 0, newMoves, lastMove);
    	
    	while (!status) {
    		searchDepth++;
    		if (searchDepth >= maximumDepth) {
    			break;
    		}
    		if((searchDepth + 1) > deepestSearch) {
    			deepestSearch = searchDepth + 1;
    		}
    		System.out.println("Starting level " + searchDepth + " search");
    		deepestSearch = searchDepth;
    		status = searchIterating(searchDepth, 0, newMoves, -1);
    	}
    	if (status) {
    		length = searchDepth;
    	}
    	return length;	
    }
    
    public boolean searchIterating(int depth, int level, Integer[] newMoves, int previousIndex) {
    	boolean sStatus = false;
    	if(level < depth) {
    		Integer[] movesIndexes = this.problem.getNoOfMoves(previousIndex);
    		
    		for (int i=0; i<movesIndexes.length; i++) {
                        int newMoveIndex = movesIndexes[i];
    			this.problem.move(newMoveIndex, this.problem);
    			
    			if (searchIterating(depth, level+1, newMoves, newMoveIndex)) {
    				sStatus = true;
    				newMoves[level] = newMoveIndex;
    				if (greed) { //This sets the solver to greedy/non greedy
    					this.problem.reverseMove(newMoveIndex, this.problem);
    					break;
    				}
    			}
    			this.problem.reverseMove(newMoveIndex, this.problem);
    		}
    	}
    	else {
    		Integer[] movesIndexes = this.problem.getNoOfMoves(previousIndex);
    		for (int i=0; i<movesIndexes.length; i++) {
                        int newMoveIndex = movesIndexes[i];
    			this.problem.move(newMoveIndex, this.problem);
    			int newHeuristic = this.heuristic();
    			
    			if (newHeuristic < oldHeuristic && newHeuristic < bestHeuristic) {
    				bestHeuristic = newHeuristic;
    				newMoves[level] = newMoveIndex;
    				sStatus = true;
    				if (greed) { //This sets the solver to greedy/non greedy
    					this.problem.reverseMove(newMoveIndex, this.problem);
    					break;
    				}
    				
    			}
    			this.problem.reverseMove(newMoveIndex, this.problem);
    		}	
    	}
    	return sStatus;
    }
        
    public int heuristic() {
        int heuristicSum = this.problem.evaluate();
    	return heuristicSum;
    }

    public String getName() {
        return "Iterative Deepening search, recursive";
    }
    
}
